package cn.lr.demo;

import org.junit.Test;

import sun.misc.Sort;


public class MajorElement {
	/**
	 * Given an array of size n, 
	 * find the majority element. The majority element is the element that appears more than [ n/2 ] times.
	 * You may assume that the array is non-empty and the majority element always exist in the array
	 */
	public int majorityElement(int[] nums) {
		int len = nums.length;
		int mid = len/2;
		int temp;
		insertSort(nums);
		//selectSort(nums);
		//quickSort(nums, 0, len-1);
		for(int a:nums){
			System.err.println(a);
		}
		return nums[mid];
    }
	//快速排序 超时
	public void quickSort(int[] nums,int left,int right){
		if(left<right){
			 int key = nums[left];
             int low = left;
             int high = right;
             while(low < high){
                 while(low < high && nums[high] >= key){
                         high--;
                 }
                 nums[low] = nums[high];
                 while(low < high && nums[low] <= key){
                         low++;
                 }
                 nums[high] = nums[low];
             }
             nums[low] = key;
             quickSort(nums,left,low-1);
             quickSort(nums,low+1,right);
		}
	}
	//选择排序  超时
	public  void selectSort(int[] numbers) {   
	    int size = numbers.length, temp;   
	    for (int i = 0; i < size; i++) {   
	        int k = i;   
	        for (int j = size - 1; j >i; j--)  {   
	            if (numbers[j] < numbers[k])  k = j;   
	        }   
	        temp = numbers[i];   
	        numbers[i] = numbers[k];   
	        numbers[k] = temp;   
	    }   
	}  
	//插入排序
	public  void insertSort(int[] numbers) {   
	    int size = numbers.length, temp, j;   
	    for(int i=1; i<size; i++) {   
	        temp = numbers[i];   
	        for(j = i; j > 0 && temp < numbers[j-1]; j--)   
	            numbers[j] = numbers[j-1];   
	        numbers[j] = temp;   
	    }
	}  
	@Test
	public void test(){
		int[] nums = {4,3,0,1};
		int a = majorityElement(nums);
		System.err.println(a);
	}

}
